package 算法.其他算法;

public class JZ83剪绳子_进阶版 {
    long mod = 998244353;
    public long cutRope (long number) {
        // write code here
        if(number<=3)
            return number-1;
        long res = number / 3;
        long num = number % 3;
        if(num==0)
            return (long) pow(3,res) % mod;
        else if(num==1)
            return (long)( pow(3,res-1) * 4 )% mod;
        else
            return ((long) pow(3,res) * 2) % mod;
    }

    long pow(long a, long n){
        long ans = 1;

        while(n>0){
            if(n%2 == 1)
                ans = (ans*a)%mod;
            a = (a*a)%mod;
            n/=2;
        }
        return ans % mod;
    }

    public static void main(String[] args) {
        System.out.println(new JZ83剪绳子_进阶版().pow(3, 3));

    }
}
